#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<stdlib.h>

using namespace std;

void Swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

int _QuickSort(int* arr, int left, int right)
{
	int rev = left, cur = rev + 1, key = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[key] && ++rev != cur)
		{
			Swap(arr[cur], arr[rev]);
		}
		cur++;
	}
	Swap(arr[rev], arr[key]);
	return rev;
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int key = _QuickSort(arr, left, right);
	QuickSort(arr, left, key - 1);
	QuickSort(arr, key + 1, right);
}

void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << ' ';
	}
	cout << endl;
}

void test1()
{
	int arr1[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
	QuickSort(arr1, 0, 8);
	PrintArr(arr1, 9);
	int arr2[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	QuickSort(arr2, 0, 9);
	PrintArr(arr2, 10);
	int arr3[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	QuickSort(arr3, 0, 9);
	PrintArr(arr3, 10);
	int arr4[] = { -3, -1, -4, -1, -5, -9, -2, -6, -5 };
	QuickSort(arr4, 0, 8);
	PrintArr(arr4, 9);
	int arr5[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4 };
	QuickSort(arr5, 0, 9);
	PrintArr(arr5, 10);
	int arr6[] = { 1 };
	QuickSort(arr6, 0, 0);
	PrintArr(arr6, 1);
}

int dp[100][100] = { 0 };

int Max(int a, int b)
{
	return (a > b) ? a : b;
}

int Func(int* value, int* weight, int n, int capacity)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= capacity; j++)
		{
			if (j >= weight[i - 1])
			{
				dp[i][j] = Max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	return dp[n][capacity];
}

void test2()
{
	int n1 = 3, c1 = 50, v1[] = { 60, 100, 120 }, w1[] = { 10, 20, 30 };
	cout << Func(v1, w1, n1, c1) << endl;
	int n2 = 2, c2 = 50, v2[] = { 100, 200 }, w2[] = { 60, 70 };
	cout << Func(v2, w2, n2, c2) << endl;
	int n3 = 3, c3 = 0, v3[] = { 10, 20, 30 }, w3[] = { 5, 10, 15 };
	cout << Func(v3, w3, n3, c3) << endl;
	int n4 = 3, c4 = 10, v4[] = { 10, 20, 30 }, w4[] = { 1, 2, 3 };
	cout << Func(v4, w4, n4, c4) << endl;
	int n5 = 1, c5 = 20, v5[] = { 100 }, w5[] = { 50 };
	cout << Func(v5, w5, n5, c5) << endl;
}


int main()
{
	test1();
	cout << "------------------------------------------" << endl;
	test2();
	return 0;
}